<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<meta name="keywords" content="spring,Spring,java,web,程序员,博客,IT,技术,移动开发,Web前端,企业架构,编程语言,互联网,数据库,技术博客,blog,分布式架构,分布式">
		<meta name="description" content="cdcoder是一个程序员学习交流平台，深度IT技术博客，移动开发博客,Web前端博客,企业架构博客,编程语言博客,互联网博客,数据库博客,IT blog,核心关注IT知识传播，共享。为更好的IT产业贡献一份微薄的力量。">
		<link rel="shortcut icon" href="/img/code.ico" />
		<link rel="bookmark" href="/img/code.ico" />
		<title>java相关知识</title>
		<link href="../css/index.css" rel="stylesheet">
		<link href="../css/github.css" rel="stylesheet" />
		<style>
			body {
				font-size: 16px;
				font: 400 16px/1.62 Georgia, "Xin Gothic", "Hiragino Sans GB", "Droid Sans Fallback", "Microsoft YaHei", sans-serif;
				font-family: 'PT serif', 微軟正黑體, 微软雅黑, 华文细黑, Microsoft Yahei, Hiragino Sans GB, sans-serif;
				color: #D0CCCC;

				text-shadow: 0px 0px 1px rgba(24, 22, 22, 0.35);
				background-color: #000;
			}
		</style>
	</head>
	<body>

		<header>
			<div class="logo"><a href="/index.html">徐思润博客</a></div>
			<nav>
				<ul id="starlist">
					<li><a href="/java/index.html">java</a></li>
					<li><a href="/data/index.html">算法与数据结构</a></li>
					<li><a href="/db/mysql.html">数据库</a></li>
					<li><a href="/distribution/index.html">分布式</a></li>
					<li><a href="/framework/index.html">架构</a></li>
					<li><a href="/interview/index.html">面试与被面试</a></li>
					<li><a href="/live/index.html">日常生活</a></li>
					<li><a href="/about.html">关于我</a></li>
					<li><a href="/baby/index.html">baby墙</a></li>
				</ul>
			</nav>
		</header>
		<div class="box">
			<h1 style="text-align: center;">树的相关总结</h1>
			<h2><strong>二叉树的优势</strong></h2>
			<h5>在实际使用时会根据链表和有序数组等数据结构的不同优势进行选择。有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链表中查找数据项效率就很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势，二叉树也是一种常用的数据结构。</h5>
			<hr />
			<p><img src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/574d0073c2da0d0a600d5c9c8d3437695444a85c7b62e8858a7cc4d78448e16427297955be34bb48a805dad45d7d6d35?pictype=scale&from=30113&version=3.3.3.3&uin=182478932&fname=20160919221509693.jpg&size=750'
				 alt='' referrerPolicy='no-referrer' /></p>
			<pre><code>  红色是根节点（root）。蓝色是子节点也是父节点，绿色的是子节点。其余的线是边。节点和链表中的节点一样都可以存放数据信息。树中的边可以用自引用表示，这种引用就是C/C++里面的指针。通常来说树是顶部小，底部大，且树呈分层结构。root节点时第0层，以此类推。二叉树最多有两个节点。
</code></pre>
			<h3>二叉树搜索</h3>
			<p> 二叉树一个节点左子节点的关键字小于这个节点，右子节点关键字大于或等于这个父节点。
				创建一个树节点
				​ 创建一个树节点包括左节点引用和右节点引用。
				//创建一个树的节点
				//每个node存放两个数据
				//一个左node引用和一个右node引用</p>
			<pre><code class='language-java' lang='java'>class Node
{
    public  int iData;
    public double dData;
    public Node leftNode;
    public Node rightNode;
    //显示树节点信息
    public void showNode()
    {
        System.out.println(&quot;{ &quot;+iData+&quot;,&quot;+dData+&quot; }&quot;);
    }
}
</code></pre>
			<p>创建一个树结构
				创建一个树结构首先是向一个树种插入数据节点。当一棵树为null时，数据项是从树的root节点处开始插入，之后的插入顺序是根据搜索节点顺序规则进行插入。具体规则是：如果数据项比父节点的数据项要小，则插在父节点的左节点（leftNode），如果比父节点的数据项要大，则将新的node插入在父节点的右节点处（rightNode）。</p>
			<pre><code class='language-java' lang='java'>private Node root;
    //插入Node
    //插入之前需要判断是否为null
    //为null需要比较大小直到currentNode为null就插入
    public void insert(int iData,double dData )
    {
        //创建node节点
        Node newNode=new Node();
        newNode.iData=iData;
        newNode.dData=dData;
        //判断root node是否为null
        if(root==null)
        {
            root=newNode;
        }
        //不为null
        else
        {
            Node current=root;
            Node parent;
            while(true)
            {
                parent=current;//保存当current变为null之前的那一个父节点
                if(iData&lt;current.iData)//插入左节点
                {
                    current=current.leftNode;//不断向左node寻找是否为null
                    if(current==null)
                    {
                        parent.leftNode=newNode;
                        return;
                    }

                }
                //插入右节点
    			else
                {
                    current=current.rightNode;
                    if(current==null)
                    {
                        parent.rightNode=newNode;
                        return;
                    }
                }
    
            }
    
        }
    }
</code></pre>
			<p>以下图表示以上插入数据节点过程：</p>
			<p><img src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/069a9c22739cfdb1ba28e4bb469144668cce7a26b465eb68875b62efd23fd71f4d9d5e428ca4e0766aa83ade72dc4d39?pictype=scale&from=30113&version=3.3.3.3&uin=182478932&fname=20160919230148150.jpg&size=750'
				 alt='' referrerPolicy='no-referrer' /></p>
			<pre><code>  在插入节点的过程中其实也就是对tree遍历的过程，最终根据条件遍历到左右节点为null时进行添加新的节点。
</code></pre>
			<h3>查找关键字</h3>
			<p>
				查找关键字是数据结构一项重要操作项，在有序数组中通过二分排序效率非常高。在二叉树中的查找效率也比较高。因为二叉树的添加node的过程就是根据数据项的大小进行有序添加的，并不是毫无秩序的插入数据项。在有序的基础上进行查找关键字效率就会快很多。
				//在tree中寻找关键字</p>
			<pre><code class='language-java' lang='java'>    //返回一个Node
    //显示这个Node
    public Node find(int key)
    {
        Node current=root;
        while(current.iData!=key)
        {
            if(current.iData&gt;key)
            {
                current=current.leftNode;
            }else
            {
                current=current.rightNode;
            }
            if(current==null)
                return null;
        }
        return current;
    }

</code></pre>
			<p>树的最值查找
				树的最值查找在树中查找是比较容易的，因为从root开始查找，最小值只会出现所有父节点的左节点处，同样最大值只会出现在所有父节点的沿着右节点搜索的最底层右节点处。
				//查找树中的最大值和最小值
				//最小值存在于一棵树的最下层的最左node
				//最大值存在于一棵树的最下层的最右node</p>
			<pre><code class='language-java' lang='java'>    public Node[] mVal()
    {
        Node minNode=null;
        Node maxNode=null;
        Node[] maxminVal=new Node[2];
        Node current=root;//从树的顶部开始搜索
        while(current!=null)
        {
            minNode=current;
            current=current.leftNode;   
        }
        maxminVal[0]=minNode;
        current=root;
        while(current!=null)
        {
            maxNode=current;
            current=current.rightNode;
        }
        maxminVal[1]=maxNode;
        return maxminVal;
    }
</code></pre>
			<p>以上是通过node数组存放两个最值，这样避免写两个方法，最后返回一个node数组。
				对以上树的操作进行测试及结果：</p>
			<pre><code class='language-java' lang='java'>Tree tree=new Tree();
        tree.insert(3, 3.666);
        tree.insert(1, 1.111);
        tree.insert(2, 2.362);
        tree.insert(4, 4.672);
        tree.insert(5, 5.865);
        tree.insert(6, 6.681);
        Node node=tree.find(6);
        if(node==null)
        {
            System.out.println(&quot;we can not find it&quot;);
        }else
        {
            node.showNode();
        }
        //查找tree中的最值
        Node[] temp=tree.mVal();
        temp[0].showNode();
        temp[1].showNode();
</code></pre>
			<p>{ 6,6.681 }
				{ 1,1.111 }
				{ 6,6.681 }</p>
			<pre><code>  由于第一个插入节点就是在root节点处进行插入，不管其数据项大小，该节点都是root节点，处于树的最顶层。
</code></pre>
			<hr />
			<p>&nbsp;</p>
			<p>&nbsp;</p>
			<h1 data-breakpage>二叉树的常见算法</h1>
			<h2>1.二叉树的遍历算法</h2>
			<p>二叉树的遍历主要分为三种：<strong>先序遍历，中序遍历和后序遍历</strong>。还有一种就是按照层次遍历。
				按照惯例，左孩子优先于右孩子，那么：</p>
			<blockquote>
				<ul>
					<li><strong>先序遍历</strong> 指的就是先访问本节点，再访问该节点的左孩子和右孩子；</li>
					<li><strong>中序遍历</strong>指的就是：先访问左孩子，再访问本节点，最后访问右孩子；</li>
					<li><strong>后序遍历</strong>指的就是：先访问左右孩子，最后访问本节点。</li>
					<li><strong>层次遍历</strong>：按照树的每一层(高度)进行遍历。</li>

				</ul>
			</blockquote>
			<p>树的节点的数据结构常声明为：</p>
			<pre><code class='language-c++' lang='c++'>struct TreeNode {
    int val;
    TreeNode *left;     //左孩子节点
    TreeNode *right;    //右孩子节点
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}

</code></pre>
			<p>约定给出根节点，分别使用三种遍历方式得到二叉树的序列：得益于递归的简洁性，三种遍历方式的递归算法也是非常简洁和易懂的。</p>
			<h3>(1). 先序遍历</h3>
			<pre><code class='language-c++' lang='c++'>//递归版本
void preOrderTraversal(vector&lt;int&gt; &amp;store, TreeNode *root) {
    if(!root) return;
    store.push_back(root-&gt;val);
    preOrderTraversal(store, root-&gt;left);   //左孩子优先
    preOrderTraversal(strore, root-&gt;right);
}

</code></pre>
			<p>先序遍历的理解：<strong>沿着最左侧通路自顶而下访问各个节点，自底而上遍历对应的右子树</strong>。迭代版本需要用到栈这种数据结构。</p>
			<pre><code class='language-c++' lang='c++'>//递归版本
void preOrderTraversal(vector&lt;int&gt; &amp;store, TreeNode *root) {
    stack&lt;TreeNode *&gt; S;
    S.push(root);
    while(!S.empty()) {
        TreeNode *curr_node = S.top();
        S.pop();
        if(curr_node) {
            store.push_back(curr_node-&gt;val);
            S.push(curr_node-&gt;right);   //左孩子优先，所以右孩子先入栈
            S.push(curr_node-&gt;left);
        }
    }
    return;
}

</code></pre>
			<h3>(2). 中序遍历</h3>
			<pre><code class='language-c++' lang='c++'>//递归版本
void inOrderTraversal(vector&lt;int&gt; &amp;store, TreeNode *root) {
    if(!root) return;
    inOrderTraversal(store, root-&gt;left);
    store.push_back(root-&gt;val);
    inOrderTraversal(store, root-&gt;right);
    return;
}

</code></pre>
			<p>中序遍历的迭代版本需要借用一个数据结构：栈，使用一个栈来保存，根节点沿着左通路一直往下访问的节点。</p>
			<pre><code class='language-c++' lang='c++'>void inorderTraversal(vector&lt;int&gt; &amp;store, TreeNode* root) {
    strack&lt;TreeNode *&gt; S;
    while(root || !S.empty()) {
        while(root) {
            S.push(root);
            root = root-&gt;left;
        }
        TreeNode *curr_node = S.top();
        S.pop();
        store.push_back(curr_node-&gt;val);
        root = curr_node-&gt;right;
    }
    return;
}

</code></pre>
			<h3>(3). 后序遍历</h3>
			<pre><code class='language-c++' lang='c++'>//递归版本
void postOrderTraversal(vector&lt;int&gt; &amp;store, TreeNode *root) {
    if(!root) return;
    postOrderTraversal(stroe, root-&gt;left);  //右孩子优先
    postOrderTraversal(stroe, root-&gt;right);
    store.push_back(root-&gt;val);
}

</code></pre>
			<p>后序遍历的迭代版本和前序遍历类似：
				可以证明，右孩子优先的先序遍历序列的逆序列就是左孩子优先的后序遍历序列。
				<img src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/27f46261a4175173a7aa44c1f55b853a17e36a2816694f85426ca0046772bb2d0ae14d755c763840b20e23570c012061?pictype=scale&from=30113&version=3.3.3.3&uin=182478932&fname=20180805162033716.png&size=750'
				 alt='Tree' referrerPolicy='no-referrer' /></p>
			<p>假设根节点的值为a，L1和R1分别是左子树和右子树在右孩子优先的先序遍历序列，L2和R2分别是左子树和右子树在左孩子优先的后序遍历序列，所以只需要证明:序列<code>&quot;a,R1,L1&quot;</code>是序列<code>&quot;L2,R2,a&quot;</code>的逆序列即可。
				从序列的组成来看，只需要证明<code>R1</code>是<code>R2</code>的逆序列且<code>L1</code>是<code>L2</code>的逆序列，显然这就将问题分解，平凡的情况下是显然成立的，因此可以归纳证明出这个结论。</p>
			<pre><code class='language-c++' lang='c++'>//迭代版本
void postOrderTraversal(vector&lt;int&gt; &amp;store, TreeNode *root) {
    stack&lt;TreeNode *&gt; S;
    S.push(root);
    while(!S.empty()) {
        TreeNode *curr_node = S.top();
        S.pop();
        if(curr_node) {
            store.push_back(curr_node-&gt;val);
            S.push(curr_node-&gt;left);    //右孩子优先，所以左孩子先入栈
            S.push(curr_node-&gt;right);
        }
    }
    std::reverse(store.begin(), store.end());   //逆序列即为所求
    return;
}

</code></pre>
			<h3>(4). 层次遍历</h3>
			<p>二叉树的按照层次遍历，需要使用数据结构队列queue，每次出队列的元素，将其左右孩子入队列。</p>
			<pre><code class='language-c++' lang='c++'>//迭代版本
void levelOrderTraversal(vector&lt;int&gt; &amp;store, TreeNode *root) {
    queue&lt;TreeNode *&gt; Q;
    Q.push(root);
    while(!Q.empty()) {
        TreeNode *curr_node = Q.front();
        if(curr_node) {
            store.push(curr_node-&gt;val);
            Q.push(curr_node-&gt;left);
            Q.push(curr_node-&gt;right);
        }
    }
    return;
}

</code></pre>
			<h2>2. 二叉树的其它算法</h2>
			<h3>(1). 二叉树的深度</h3>
			<p>递归版本非常简洁，也非常易懂；迭代版本则需要利用我们之前介绍的按照层次遍历，层数就是二叉树的深度。</p>
			<pre><code class='language-c++' lang='c++'>//递归版本
int TreeDepth(TreeNode *pRoot) {
    return pRoot ? 1 + max(TreeDepth(pRoot-&gt;left),
                           TreeDepth(pRoot-&gt;right)) : 0;
}
//迭代版本
int TreeDepth2(TreeNode *pRoot) {
    queue&lt;TreeNode *&gt; Q;
    Q.push(pRoot);
    int depth = 0;
    while(!Q.empty()) {
        int len = Q.size();
        ++depth;
        while(len--) {
            TreeNode *curr_node = Q.front();
            Q.pop();
            if(curr_node) {
                Q.push(curr_node-&gt;left);
                Q.push(curr_node-&gt;right);
            }
        }
    }
    return depth - 1;   //将叶节点的空孩子节点也算作一层了，所以减1
}


</code></pre>
			<h3>(2). 二叉树的镜像</h3>
			<p>操作给定的二叉树，将其变换为源二叉树的镜像。使用递归，当节点存在至少一个孩子时，交换左右孩子，再递归处理。</p>
			<pre><code class='language-c++' lang='c++'>//二叉树的镜像
void Mirror(TreeNode *pRoot) {
	if (pRoot &amp;&amp; (pRoot-&gt;left || pRoot-&gt;right)) {
        std::swap(pRoot-&gt;left, pRoot-&gt;right);
		Mirror(pRoot-&gt;left);
        Mirror(pRoot-&gt;right);
	}
	return;
}

</code></pre>
			<h3>(3). 平衡二叉树</h3>
			<p>输入一棵二叉树，判断该二叉树是否是平衡二叉树。
				平衡二叉树指的是：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，<a href='https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91'>见百度百科</a>。<strong>关键点：子树的高度差不超过1且子树也是平衡树</strong>。构造一个递归函数<code>IsBalanced</code>来判断这两个条件。</p>
			<pre><code class='language-c++' lang='c++'>//平衡二叉树
bool IsBalanced(TreeNode *pRoot, int &amp;pDepth) {
	if (!pRoot) {
		pDepth = 0;
		return true;
	}
	int left_depth, right_depth;    //记录左右子树的高度
	if (IsBalanced(pRoot-&gt;left, left_depth) &amp;&amp;
	    IsBalanced(pRoot-&gt;right, right_depth)) {
		int diff = left_depth - right_depth;
		if (diff &lt;= 1 &amp;&amp; diff &gt;= -1) {
			pDepth = 1 + (left_depth &gt; right_depth ? left_depth : right_depth);
			return true;
		}
	}
	return false;
}
bool IsBalanced_Solution(TreeNode *pRoot) {
	int pDepth = 0;
	return IsBalanced(pRoot, pDepth);
}

</code></pre>
			<h3>(4). 对称的二叉树</h3>
			<p>请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。</p>
			<pre><code class='language-c++' lang='c++'>//对称的二叉树
bool isSymmetrical(TreeNode *leftChild, TreeNode *rightChild) {
	if (!leftChild &amp;&amp; !rightChild) {
		//左右子树同时为空
		return true;
	}
	else if (leftChild &amp;&amp; rightChild) {
		//左右子树都不为空
		return leftChild-&gt;val == rightChild-&gt;val &amp;&amp;
			   isSymmetrical(leftChild-&gt;left, rightChild-&gt;right) &amp;&amp;
			   isSymmetrical(leftChild-&gt;right, rightChild-&gt;left);
	}
	else {
		return false;
	}
}
bool isSymmetrical(TreeNode *pRoot) {
	if (!pRoot) return true; 
	return isSymmetrical(pRoot-&gt;left, pRoot-&gt;right);
}

</code></pre>
			<h3>(5). 把二叉树打印成多行</h3>
			<p>从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
				在求二叉树的深度的时候，迭代解法起始我们已经做了这个事情，只是没有按照多行输出，所以只需要记录每一行的<code>val</code>即可。</p>
			<pre><code class='language-c++' lang='c++'>//把二叉树打印成多行
vector&lt;vector&lt;int&gt;&gt; Print(TreeNode *pRoot) {
	vector&lt;vector&lt;int&gt;&gt; store;
	queue&lt;TreeNode *&gt; Q;
	Q.push(pRoot);
	int index = 0;
	while (!Q.empty()) {
		int length = Q.size();
		store.push_back(vector&lt;int&gt;());
		while (length--) {
			TreeNode *curr_node = Q.front();
			Q.pop();
			if (curr_node) {
				store[index].push_back(curr_node-&gt;val);
				Q.push(curr_node-&gt;left);
				Q.push(curr_node-&gt;right);
			}
		}
		++index;
	}
	store.pop_back();   //将叶节点的空孩子节点也算作一层了，所以pop_back()
	return store;
}


</code></pre>
			<h3>(6). 二叉树的下一个结点</h3>
			<p>给定一个二叉树和其中的一个结点，请找出<strong>中序遍历</strong>顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
				节点的数据结构表示为：</p>
			<pre><code class='language-c++' lang='c++'>struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;  //父节点
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {}
};

</code></pre>
			<p>若允许一定的<strong>空间复杂度</strong>，可以直接<strong>中序遍历保存序列</strong>之后直接查找。这种方法就不介绍了，下面介绍常数空间的算法：</p>
			<ul>
				<li>如果该<strong>节点有右孩子</strong>，必然下一个节点就是该节点的右孩子的沿着左侧链下的最后一个左孩子；</li>
				<li>该节点<strong>没有右孩子，也没有父节点</strong>，说明这个节点是最后一个节点；</li>
				<li>该节点<strong>没有右孩子，但是有父节点且是父节点的左孩子</strong>，必然下一个节点就是该节点的父节点；</li>
				<li>该节点<strong>没有右孩子，且有父节点且是父节点的右孩子</strong>，要么该节点是最后一个节点，要么沿着父链上升，之后第一个节点的是其父节点的左孩子，这个父节点就是下一个节点。</li>

			</ul>
			<pre><code class='language-c++' lang='c++'>//二叉树的下一个结点
TreeLinkNode *GetNext(TreeLinkNode *pNode) {
	if (!pNode) return pNode;
	if (pNode-&gt;right) {		//有右孩子的情况
		pNode = pNode-&gt;right;
		while (pNode-&gt;left) {
			pNode = pNode-&gt;left;
		}
		return pNode;
	} 
	else {		//没有右孩子的情况
		TreeLinkNode *parent = pNode-&gt;next;
		if (!parent) {
			return parent;
		} 
		else {
			if (pNode == parent-&gt;left) {	//该节点是其父节点的左孩子
				return parent;
			} 
			else {	//该节点是其父节点的右孩子，沿左侧链上升
				while (parent-&gt;next &amp;&amp; parent == parent-&gt;next-&gt;right) {
					parent = parent-&gt;next;
				}
				return parent-&gt;next;
			}
		}
	}
}

</code></pre>
			<h3>(7). 二叉搜索树与双向链表</h3>
			<p>输入一棵二叉搜索树，将该二叉搜索树转换成一个<strong>排序的双向链表</strong>。要求不能创建任何新的结点，只能调整树中结点指针的指向。
				二叉搜索树(Binary Search Tree, BST)：它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
				若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。<a href='https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91/7077855'>详见百度百科</a>。
				中序遍历一颗二叉搜索树，必然得到的是一个有序的序列。</p>
			<pre><code class='language-c++' lang='c++'>void recurConvert(TreeNode *root, TreeNode *&amp;pre) {
  if (!root) return;
  recurConvert(root-&gt;left, pre);
  root-&gt;left = pre;
  if (pre) pre-&gt;right = root;
  pre = root;
  recurConvert(root-&gt;right, pre);
}
TreeNode *Convert(TreeNode *pRootOfTree) {
  if (!pRootOfTree) return pRootOfTree;
  TreeNode *pre = 0;
  recurConvert(pRootOfTree, pre);
  TreeNode *res = pRootOfTree;
  while (res-&gt;left) res = res-&gt;left;
  return res;
}
12345678910111213141516

</code></pre>
			<h3>(8). 二叉树中和为某一值的路径</h3>
			<p>输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)</p>
			<pre><code class='language-c++' lang='c++'>//二叉树中和为某一值的路径
void FindPath(vector&lt;vector&lt;int&gt;&gt; &amp;vec_store, 
			  vector&lt;int&gt; store,
			  TreeNode *root,
              int expNumber) {
	store.push_back(root-&gt;val);
	if (!root-&gt;left &amp;&amp; !root-&gt;right) {
		if (expNumber == root-&gt;val) vec_store.push_back(store);
		return;
	}
	if (root-&gt;left) 
	    FindPath(vec_store, store, root-&gt;left, expNumber - root-&gt;val);
	if (root-&gt;right) 
	    FindPath(vec_store, store, root-&gt;right, expNumber - root-&gt;val);
	store.pop_back();		//回溯
}
vector&lt;vector&lt;int&gt;&gt; FindPath(TreeNode *root, int expectNumber) {
    vector&lt;vector&lt;int&gt;&gt; vec_store;
	vector&lt;int&gt; store;
	if(root) FindPath(vec_store, store, root, expectNumber);
	return vec_store;
}
 

</code></pre>
			<h3>(9). 按之字形顺序打印二叉树</h3>
			<p>请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行<a href='https://www.baidu.com/s?wd=%E4%BB%A5%E6%AD%A4%E7%B1%BB%E6%8E%A8&tn=24004469_oem_dg&rsv_dl=gh_pl_sl_csd'>以此类推</a>。
				思路，构建两个栈，依次保存奇数行和偶数行的节点，注意左右孩子的入栈顺序；例如：从第0行到第1行，第1行先左孩子，再右孩子入栈，这样出栈的时候才会从右往左的顺序；从第1行到第2行，先右孩子，再左孩子入栈，这样才能保证出栈的顺序是从左往右。</p>
			<pre><code class='language-c++' lang='c++'>//按之字形顺序打印二叉树
vector&lt;vector&lt;int&gt;&gt; Print(TreeNode *pRoot) {
	if (!pRoot) return {};
	vector&lt;vector&lt;int&gt;&gt; result;
	stack&lt;TreeNode *&gt; odd, even;
	even.push(pRoot);		//从第零行开始
	while (!even.empty() || !odd.empty()) {
		vector&lt;int&gt; line;
		if (odd.empty()) {
			while (!even.empty()) {
				TreeNode *curr_node = even.top();
				even.pop();
				line.push_back(curr_node-&gt;val);
				if (curr_node-&gt;left) odd.push(curr_node-&gt;left);
				if (curr_node-&gt;right) odd.push(curr_node-&gt;right);	//注意，先左后右
			}
		}
		else {
			while (!odd.empty()) {
				TreeNode *curr_node = odd.top();
				odd.pop();
				line.push_back(curr_node-&gt;val);
				if (curr_node-&gt;right) even.push(curr_node-&gt;right);
				if (curr_node-&gt;left) even.push(curr_node-&gt;left);		//注意，先右后左
			}			
		}
		result.push_back(line);
	}
	return result;
}
 

</code></pre>
			<h3>10. 二叉搜索树的第k个结点</h3>
			<p>给定一棵二叉搜索树，请找出其中的第k小的结点。例如： <code>（5，3，7，2，4，6，8）</code> 中，按结点数值大小顺序第三小结点的值为4。 如果按照中序遍历存储起来，这种思路是非常简单且容易实现的：</p>
			<pre><code class='language-c++' lang='c++'>void inOrderTraversal(TreeNode *pRoot, vector&lt;TreeNode *&gt; &amp;store) {
    if(!pRoot) return;
    inOrderTraversal(pRoot-&gt;left, store);
    store.push_back(pRoot);
    inOrderTraversal(pRoot-&gt;right, store);
}
TreeNode* KthNode(TreeNode *pRoot, int k) {
    vector&lt;TreeNode *&gt; store;
    inOrderTraversal(pRoot, store);
    return k &gt; 0 &amp;&amp; k &lt;= store.size() ? store[k - 1] : nullptr;
}


</code></pre>
			<h3>11. 二叉搜索树的后序遍历序列</h3>
			<p>输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
				对于后序遍历，我们知道序列最后一个数字必定是二叉搜索树的根节点，由于保证序列的任意两个数字都互不相同，设序列中第一个大于根节点的位置为k，那么<code>[0,k)</code>这一段子序列必然是<strong>左子树后序遍历得到的子序列</strong>，<code>[k+1,
					end)</code>必然是<strong>右子树后序遍历得到的子序列</strong>，依此递归即可，另外，在<code>[k+1, end)</code>若存在有<strong>一个节点的值小于根节点</strong>，说明不是二叉搜索树的后序遍历序列
				。</p>
			<pre><code class='language-c++' lang='c++'>//二叉搜索树的后序遍历序列
bool judgeBST(vector&lt;int&gt;::iterator first, vector&lt;int&gt;::iterator last) {
	if (last == first) return true;
	int root_val = *(last - 1);
	auto iter = first;
	while (iter &lt; last - 1) {
		if (*iter &gt; root_val) break;
		++iter;
	}
	auto temp = iter;
	while (iter &lt; last - 1) {
		if (*iter  &lt;= root_val) return false;
		++iter;
	}
	return judgeBST(first, temp) &amp;&amp; judgeBST(temp, last - 1);
}
bool VerifySquenceOfBST(vector&lt;int&gt; sequence) {
	if (sequence.empty()) return false;
	return judgeBST(sequence.begin(), sequence.end());
}

</code></pre>
			<h3>11. 重建二叉树</h3>
			<p>输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列<code>{1,2,4,7,3,5,6,8}</code>和中序遍历序列<code>{4,7,2,1,5,3,8,6}</code>，则重建二叉树并返回。</p>
			<pre><code class='language-c++' lang='c++'>//重建二叉树
TreeNode *reConstructBinaryTree(vector&lt;int&gt;::iterator pre_first, 
							vector&lt;int&gt;::iterator pre_last,
                                vector&lt;int&gt;::iterator vin_first,
                                vector&lt;int&gt;::iterator vin_last) {
	if (vin_last - vin_first != pre_last - pre_first ||
			pre_last == pre_first ||
			vin_first == vin_last) {
		return nullptr;
	}
	TreeNode *curr_node = new TreeNode(*pre_first);
	if (pre_last == pre_first + 1) return curr_node;
	auto iter = vin_first;
	while (iter &lt; vin_last) {
		if (*iter == *pre_first) break;
        iter++;
	}
	int len = iter - vin_first;
	curr_node-&gt;left = reConstructBinaryTree(pre_first + 1, pre_first + len + 1, vin_first, iter);
	curr_node-&gt;right = reConstructBinaryTree(pre_first + len + 1, pre_last, iter + 1, vin_last);
	return curr_node;
}
TreeNode *reConstructBinaryTree(vector&lt;int&gt; pre, vector&lt;int&gt; vin) {
  return reConstructBinaryTree(pre.begin(), pre.end(), vin.begin(), vin.end());
}


</code></pre>
			<h3>12. 树的子结构</h3>
			<p>输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）</p>
			<pre><code class='language-c++' lang='c++'>//树的子结构
bool isSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
  //判断以pRoot2为根节点的树是否是以pRoot1为根节点的树的子树
	if (!pRoot2) return true;
	if (!pRoot1) return false;
	return pRoot1-&gt;val != pRoot2-&gt;val ? false :
		   isSubtree(pRoot1-&gt;left, pRoot2-&gt;left) &amp;&amp;
		   isSubtree(pRoot1-&gt;right, pRoot2-&gt;right);
}
bool HasSubtree(TreeNode *pRoot1, TreeNode *pRoot2) {
	if(!pRoot1 || !pRoot2) return false;
	return isSubtree(pRoot1, pRoot2) ||
		   isSubtree(pRoot1-&gt;left, pRoot2) ||
		   isSubtree(pRoot1-&gt;right, pRoot2);
}

</code></pre>
			<p>&nbsp;</p>
			<h3>二叉树基本概念</h3>
			<p>二叉树在图论中是这样定义的：</p>
			<p><code>二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。</code></p>
			<h3>二叉树性质如下：</h3>
			<ol>
				<li>二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。</li>
				<li>二叉树的第 i 层至多有 2i−12i−1 个结点。</li>
				<li>深度为 k 的二叉树至多有 2k−12k−1 个结点。</li>
				<li>对任何一棵二叉树T，如果其终端结点数为n0n0，度为2的结点数为n2n2，则n0=n2+1n0=n2+1。</li>
				<li>一棵深度为k，且有 2k−12k−1 个节点称之为满二叉树；</li>
				<li>深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。</li>
				<li>平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。</li>

			</ol>
			<h3>二叉树中树节点的数据结构</h3>
			<p>二叉树由一系列树结点组成，每个结点包括三个部分：</p>
			<ul>
				<li>一个是存储数据元素的数据域，</li>
				<li>另一个是存储左子结点地址的指针域，</li>
				<li>另一个是存储右子结点地址的指针域。</li>

			</ul>
			<p>定义树节点为类：TreeNode。具体实现如下：</p>
			<pre><code class='language-java' lang='java'>public class TreeNode {
    public int val; // 数据域
    public TreeNode left; // 左子树根节点
    public TreeNode right; // 右子树根节点
    
    public TreeNode() {
    
    }
    
    public TreeNode(int val) {
        this.val = val;
    }
}

</code></pre>
			<h3>二叉树的遍历</h3>
			<ol>
				<li>
					<h4><strong>前序遍历</strong></h4>
					<h5>递归解法：</h5>
				</li>

			</ol>
			<p>如果二叉树为空，空操作
				如果二叉树不为空，访问根节点，前序遍历左子树，前序遍历右子树</p>
			<pre><code class='language-java' lang='java'>/**
 * 1. 前序遍历
 * 递归
 * @param root 树根节点
   */
   public static void preorderTraversalRec(TreeNode root){
   if (root == null) {
       return;
   }
   System.out.print(root.val + &quot;-&gt;&quot;);
   preorderTraversalRec(root.left);
   preorderTraversalRec(root.right);
   }

</code></pre>
			<p> 非递归解法：用一个辅助stack，总是先把右孩子放进栈。</p>
			<pre><code class='language-java' lang='java'>/**
 * 1. 前序遍历
 * 非递归
 * @param root 树根节点
    */
    public static void preorderTraversal2(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;(); // 辅助栈
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { // 不断将左子节点入栈，直到cur为空
            stack.push(cur);
            System.out.print(cur.val + &quot;-&gt;&quot;); // 前序遍历，先打印当前节点在打印左子节点，然后再把右子节点加到栈中
            cur = cur.left;
        }
        if (!stack.isEmpty()) { // 栈不为空，弹出栈元素
            cur = stack.pop(); // 此时弹出最左边的节点
            cur = cur.right; // 令当前节点为右子节点
        }
    }
    }

/**
 * 1. 前序遍历
 * 非递归解法2
 * @param root 树根节点
    */
    public static void preorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;(); // 辅助栈保存树节点
    stack.add(root);
    while (!stack.isEmpty()) { // 栈不为空
        TreeNode temp = stack.pop();
        System.out.print(temp.val + &quot;-&gt;&quot;); // 先根节点，因为是前序遍历
        if (temp.right != null) { // 先添加右孩子，因为栈是先进后出
            stack.add(temp.right);
        }
        if (temp.left != null) {
            stack.add(temp.left);
        }
    }
    }

</code></pre>
			<ol start='2'>
				<li>
					<h4>中序遍历</h4>
					<h5>递归解法：</h5>
				</li>

			</ol>
			<p>如果二叉树为空，空操作
				如果二叉树不为空，中序遍历左子树，访问根节点，中序遍历右子树</p>
			<pre><code class='language-java' lang='java'>/**
 * 2. 中序遍历
 * 递归
 * @param root 树根节点
    */
    public static void inorderTraversalRec(TreeNode root){
    if (root == null) {
        return;
    }
    inorderTraversalRec(root.left);
    System.out.print(root.val + &quot;-&gt;&quot;);
    inorderTraversalRec(root.right);
    }

</code></pre>
			<pre><code>非递归解法：用栈先把根节点的所有左孩子都添加到栈内，然后输出栈顶元素，再处理栈顶元素的右子树。

</code></pre>
			<pre><code class='language-java' lang='java'>/**
 * 2. 中序遍历
 * 非递归
 * @param root 树根节点
    */
    public static void inorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;(); // 辅助栈
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) { // 不断将左子节点入栈，直到cur为空
            stack.push(cur);
            cur = cur.left;
        }
        if (!stack.isEmpty()) { // 栈不为空，弹出栈元素
            cur = stack.pop(); // 此时弹出最左边的节点
            System.out.print(cur.val + &quot;-&gt;&quot;); // 中序遍历，先打印左子节点在打印当前节点，然后再把右子节点加到栈中
            cur = cur.right; // 令当前节点为右子节点
        }
    }
    }

</code></pre>
			<ol start='3'>
				<li>
					<h4>后序遍历</h4>
					<h5>递归解法：</h5>
				</li>

			</ol>
			<p>如果二叉树为空，空操作
				如果二叉树不为空，后序遍历左子树，后序遍历右子树，访问根节点</p>
			<pre><code class='language-java' lang='java'>/**
 * 3. 后序遍历
 * 递归
 * @param root 树根节点
    */
    public static void postorderTraversalRec(TreeNode root){
    if (root == null) {
        return;
    }
    postorderTraversalRec(root.left);
    postorderTraversalRec(root.right);
    System.out.print(root.val + &quot;-&gt;&quot;);
    }

    非递归解法：双栈法。

/**
 * 3. 后序遍历
 * 非递归
 * @param root 树根节点
    */
    public static void postorderTraversal(TreeNode root) {
    if(root == null) {
        return;
    }
    Stack&lt;TreeNode&gt; stack1 = new Stack&lt;&gt;(); // 保存树节点
    Stack&lt;TreeNode&gt; stack2 = new Stack&lt;&gt;(); // 保存后序遍历的结果
    stack1.add(root);
    while (!stack1.isEmpty()) {
        TreeNode temp = stack1.pop();
        stack2.push(temp); // 将弹出的元素加到stack2中
        if (temp.left != null) { // 左子节点先入栈
            stack1.push(temp.left);
        }
        if (temp.right != null) { // 右子节点后入栈
            stack1.push(temp.right);
        }
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + &quot;-&gt;&quot;);
    }
    }

</code></pre>
			<ol start='4'>
				<li>层次遍历
					思路：分层遍历二叉树（按层次从上到下，从左到右）迭代，相当于广度优先搜索，使用队列实现。队列初始化，将根节点压入队列。当队列不为空，进行如下操作：弹出一个节点，访问，若左子节点或右子节点不为空，将其压入队列。</li>

			</ol>
			<pre><code class='language-c++' lang='c++'>/**
 * 4. 层次遍历
 * @param root 根节点
    */
    public static void levelTraversal(TreeNode root){
    if(root == null) {
        return;
    }
    Queue&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;(); // 对列保存树节点
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode temp = queue.poll();
        System.out.print(temp.val + &quot;-&gt;&quot;);
        if (temp.left != null) { // 添加左右子节点到对列
            queue.add(temp.left);
        }
        if (temp.right != null) {
            queue.add(temp.right);
        }
    }
    }

</code></pre>
			<pre><code>常见的二叉树算法题

</code></pre>
			<ol>
				<li>
					<p>求二叉树中的节点个数
						递归解法： O(n)O(n)
						如果二叉树为空，节点个数为0
						如果二叉树不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1</p>
					<pre><code class='language-java' lang='java'>/**
 * 1. 求二叉树中的节点个数
 * 递归
 * @param root 树根节点
 * @return 节点个数
 */
public static int getNodeNumRec(TreeNode root) {
if (root == null) {
    return 0;
}
return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
}

</code></pre>
					<p>非递归解法：O(n)O(n)。基本思想同LevelOrderTraversal。即用一个Queue，在Java里面可以用LinkedList来模拟。</p>
					<pre><code>
</code></pre>
				</li>

			</ol>
			<pre><code class='language-java' lang='java'>/**
 * 1. 求二叉树中的节点个数
 * 非递归
 * @param root 树根节点
 * @return 节点个数
    */
    public static int getNodeNum(TreeNode root) {
    if (root == null) {
        return 0;
    }
    Queue&lt;TreeNode&gt; queue =  new LinkedList&lt;&gt;(); // 用队列保存树节点，先进先出
    queue.add(root);
    int count = 1; // 节点数量
    while (!queue.isEmpty()) {
        TreeNode temp = queue.poll(); // 每次从对列中删除节点，并返回该节点信息
        if (temp.left != null) { // 添加左子孩子到对列
            queue.add(temp.left);
            count++;
        }
        if (temp.right != null) { // 添加右子孩子到对列
            queue.add(temp.right);
            count++;
        }
    }
    return count;
    }

</code></pre>
			<ol start='2'>
				<li>求二叉树的深度（高度）
					递归解法： O(n)O(n)
					如果二叉树为空，二叉树的深度为0
					如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 1</li>

			</ol>
			<pre><code class='language-java' lang='java'>    /**
     * 求二叉树的深度（高度） 
     * 递归
     * @return 树的深度
  	 */
  public static int getDepthRec(TreeNode root) {
   if (root == null) {
       return 0;
   }
   return Math.max(getDepthRec(root.left), getDepthRec(root.right)) + 1;
  }

</code></pre>
			<p> 非递归解法：O(n)O(n)。基本思想同LevelOrderTraversal。即用一个Queue，在Java里面可以用LinkedList来模拟。</p>
			<pre><code class='language-java' lang='java'>/**
 * 求二叉树的深度（高度）
 * 非递归
 * @param root 树根节点
 * @return 树的深度
    */
    public static int getDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int currentLevelCount = 1; // 当前层的节点数量
    int nextLevelCount = 0; // 下一层节点数量
    int depth = 0; // 树的深度

    Queue&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;(); // 对列保存树节点
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode temp = queue.remove(); // 移除节点
        currentLevelCount--; // 当前层节点数减1
        if (temp.left != null) { // 添加左节点并更新下一层节点个数
            queue.add(temp.left);
            nextLevelCount++;
        }
        if (temp.right != null) { // 添加右节点并更新下一层节点个数
            queue.add(temp.right);
            nextLevelCount++;
        }
        if (currentLevelCount == 0) { // 如果是该层的最后一个节点，树的深度加1
            depth++;
            currentLevelCount = nextLevelCount; // 更新当前层节点数量并且重置下一层节点数量
            nextLevelCount = 0;
        }
    }
    return depth;
    }

</code></pre>
			<ol start='3'>
				<li>求二叉树第k层的节点个数
					递归解法： O(n)O(n)
					思路：求以root为根的k层节点数目，等价于求以root左孩子为根的k-1层（因为少了root）节点数目 加上以root右孩子为根的k-1层（因为 少了root）节点数目。即：</li>

			</ol>
			<p>如果二叉树为空或者k&lt;1，返回0
				如果二叉树不为空并且k==1，返回1
				如果二叉树不为空且k&gt;1，返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和</p>
			<pre><code class='language-java' lang='java'>/**
 * 求二叉树第k层的节点个数
 * 递归
 * @param root 根节点
 * @param k 第k个节点
 * @return 第k层节点数
    */
    public static int getNodeNumKthLevelRec(TreeNode root, int k) {
    if (root == null || k &lt; 1) {
        return 0;
    }
    if (k == 1) {
        return 1;
    }
    return getNodeNumKthLevelRec(root.left, k - 1) + getNodeNumKthLevelRec(root.right, k - 1);
    }

</code></pre>
			<ol start='4'>
				<li>求二叉树中叶子节点的个数
					递归解法：</li>

			</ol>
			<p>如果二叉树为空，返回0
				如果二叉树是叶子节点，返回1
				如果二叉树不是叶子节点，二叉树的叶子节点数 = 左子树叶子节点数 + 右子树叶子节点数</p>
			<pre><code class='language-java' lang='java'>/**
 * 4. 求二叉树中叶子节点的个数
 * 递归
 * @param root 根节点
 * @return 叶子节点个数
    */
    public static int getNodeNumLeafRec(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null &amp;&amp; root.right == null) {
        return 1;
    }
    return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);
    }

    非递归解法：基于层次遍历进行求解，利用Queue进行。

 /**
 * 4. 求二叉树中叶子节点的个数（迭代）
 * 非递归
 * @param root 根节点
 * @return 叶子节点个数
    */
    public static int getNodeNumLeaf(TreeNode root){
    if (root == null) {
        return 0;
    }
    int leaf = 0; // 叶子节点个数
    Queue&lt;TreeNode&gt; queue = new LinkedList&lt;&gt;();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode temp = queue.poll();
        if (temp.left == null &amp;&amp; temp.right == null) { // 叶子节点
            leaf++;
        }
        if (temp.left != null) {
            queue.add(temp.left);
        }
        if (temp.right != null) {
            queue.add(temp.right);
        }
    }
    return leaf;
    }

</code></pre>
			<ol start='5'>
				<li>判断两棵二叉树是否相同的树
					递归解法：</li>

			</ol>
			<p>如果两棵二叉树都为空，返回真
				如果两棵二叉树一棵为空，另外一棵不为空，返回假
				如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假</p>
			<pre><code class='language-java' lang='java'>/**
 * 5. 判断两棵二叉树是否相同的树。
 * 递归
 * @param r1 二叉树1
 * @param r2 二叉树2
 * @return 是否相同
    */
    public static boolean isSameRec(TreeNode r1, TreeNode r2) {
    if (r1 == null &amp;&amp; r2 == null) { // 都是空
        return true;
    } else if (r1 == null || r2 == null) { // 有一个为空，一个不为空
        return false;
    }
    if (r1.val != r2.val) { // 两个不为空，但是值不相同
        return false;
    }
    return isSameRec(r1.left, r2.left) &amp;&amp; isSameRec(r1.right, r2.right); // 递归遍历左右子节点
    }

</code></pre>
			<pre><code>非递归解法：利用Stack对两棵树对应位置上的节点进行判断是否相同。

</code></pre>
			<pre><code class='language-java' lang='java'>    /**
     * 5. 判断两棵二叉树是否相同的树（迭代）
     * 非递归
     * @param r1 二叉树1
     * @param r2 二叉树2
     * @return 是否相同
     */
    public static boolean isSame(TreeNode r1, TreeNode r2){
    if (r1 == null &amp;&amp; r2 == null) { // 都是空
        return true;
    } else if (r1 == null || r2 == null) { // 有一个为空，一个不为空
        return false;
    }
    Stack&lt;TreeNode&gt; stack1 = new Stack&lt;&gt;();
    Stack&lt;TreeNode&gt; stack2 = new Stack&lt;&gt;();
    stack1.add(r1);
    stack2.add(r2);
    while (!stack1.isEmpty() &amp;&amp; !stack2.isEmpty()) {
        TreeNode temp1 = stack1.pop();
        TreeNode temp2 = stack2.pop();
        if (temp1 == null &amp;&amp; temp2 == null) { // 两个元素都为空，因为添加的时候没有对空节点做判断
            continue;
        } else if (temp1 != null &amp;&amp; temp2 != null &amp;&amp; temp1.val == temp2.val) {
            stack1.push(temp1.left); // 相等则添加左右子节点判断
            stack1.push(temp1.right);
            stack2.push(temp2.left);
            stack2.push(temp2.right);
        } else {
            return false;
        }
    }
    return true;
    }

</code></pre>
			<ol start='6'>
				<li>判断二叉树是不是平衡二叉树
					递归实现：借助前面实现好的求二叉树高度的函数</li>

			</ol>
			<p>如果二叉树为空， 返回真
				如果二叉树不为空，如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1，返回真，其他返回假</p>
			<pre><code class='language-java' lang='java'>    /**
     *  判断二叉树是不是平衡二叉树
     * 递归
     * @param root 根节点
     * @return 是否二叉平衡树（AVL树）
     */
    public static boolean isAVLTree(TreeNode root) {
    if (root == null) {
        return true;
    }
    if (Math.abs(getDepth(root.left) - getDepth(root.right)) &gt; 1) { // 左右子树高度差大于1
        return false;
    }
    return isAVLTree(root.left) &amp;&amp; isAVLTree(root.right); // 递归判断左右子树
    }

</code></pre>
			<ol start='7'>
				<li>求二叉树的镜像
					递归实现：破坏原来的树，把原来的树改成其镜像</li>

			</ol>
			<p>如果二叉树为空，返回空
				如果二叉树不为空，求左子树和右子树的镜像，然后交换左右子树</p>
			<pre><code class='language-java' lang='java'>    /**
     * 7. 求二叉树的镜像
     * 递归
     * @param root 根节点
     * @return 镜像二叉树的根节点
     */
    public static TreeNode mirrorRec(TreeNode root) {
    if (root == null) {
        return root;
    }
    TreeNode left = mirrorRec(root.right); // 递归镜像左右子树
    TreeNode right = mirrorRec(root.left);
    root.left = left; // 更新根节点的左右子树为镜像后的树
    root.right = right;
    return root;
    }

</code></pre>
			<pre><code>递归实现：不能破坏原来的树，返回一个新的镜像树

</code></pre>
			<p>如果二叉树为空，返回空
				如果二叉树不为空，求左子树和右子树的镜像，然后交换左右子树</p>
			<pre><code class='language-java' lang='java'>    /**
     * 7. 求二叉树的镜像
     * 递归
     * @param root 根节点
     * @return 镜像二叉树的根节点
     */
    public static TreeNode mirrorCopyRec(TreeNode root) {
    if (root == null) {
        return root;
    }
    TreeNode newRoot = new TreeNode(root.val); // 创建新节点，然后交换左右子树
    newRoot.left = mirrorCopyRec(root.right);
    newRoot.right = mirrorCopyRec(root.left);
    return newRoot;
    }

</code></pre>
			<pre><code>非递归实现：破坏原来的树，把原来的树改成其镜像

</code></pre>
			<pre><code class='language-java' lang='java'>    /**
     * 7. 求二叉树的镜像
     * 非递归
     * @param root 根节点
     * @return 镜像二叉树的根节点
     */
    public static void mirror(TreeNode root) {
    if (root == null) {
        return ;
    }
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode cur = stack.pop();
        // 交换左右孩子
        TreeNode tmp = cur.right;
        cur.right = cur.left;
        cur.left = tmp;

        if(cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }

    }
    }

</code></pre>
			<pre><code>非递归实现：不能破坏原来的树，返回一个新的镜像树

</code></pre>
			<pre><code class='language-java' lang='java'>    /**
     * 7. 求二叉树的镜像
     * 非递归
     * @param root 根节点
     * @return 镜像二叉树的根节点
     */
    public static TreeNode mirrorCopy(TreeNode root) {
    if (root == null) {
        return null;
    }
    Stack&lt;TreeNode&gt; stack = new Stack&lt;TreeNode&gt;();
    Stack&lt;TreeNode&gt; newStack = new Stack&lt;TreeNode&gt;();
    stack.push(root);
    TreeNode newRoot = new TreeNode(root.val);
    newStack.push(newRoot);
    while (!stack.isEmpty()) {
        TreeNode cur = stack.pop();
        TreeNode newCur = newStack.pop();
        if (cur.right != null) {
            stack.push(cur.right);
            newCur.left = new TreeNode(cur.right.val);
            newStack.push(newCur.left);
        }
        if (cur.left != null) {
            stack.push(cur.left);
            newCur.right = new TreeNode(cur.left.val);
            newStack.push(newCur.right);
        }
    }
    return newRoot;
    }

</code></pre>
			<ol start='8'>
				<li>判断两个二叉树是否互相镜像
					递归解法：与比较两棵二叉树是否相同解法一致（题5），非递归解法省略。</li>

			</ol>
			<p>比较r1的左子树的镜像是不是r2的右子树
				比较r1的右子树的镜像是不是r2的左子树</p>
			<pre><code class='language-java' lang='java'>    /**
     * 8. 判断两个树是否互相镜像
     * @param r1 二叉树 1
     * @param r2 二叉树 2
     * @return 是否互相镜像
     */
    public static boolean isMirrorRec(TreeNode r1, TreeNode r2) {
    if (r1 == null &amp;&amp; r2 == null) {
        return true;
    } else if (r1 == null || r2 == null) {
        return false;
    }
    if (r1.val != r2.val) {
        return false;
    }
    // 递归比较r1的左子树的镜像是不是r2右子树
    // 和r1的右子树的镜像是不是r2的左子树
    return isMirrorRec(r1.left, r2.right) &amp;&amp; isMirrorRec(r1.right, r2.left);
    }

</code></pre>
			<ol start='9'>
				<li>求二叉树中两个节点的最低公共祖先节点
					递归解法：</li>

			</ol>
			<p>如果两个节点分别在根节点的左子树和右子树，则返回根节点
				如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树</p>
			<pre><code class='language-java' lang='java'>    /**
     * 9. 求二叉树中两个节点的最低公共祖先节点
     * 递归
     * @param root 树根节点
     * @param n1 第一个节点
     * @param n2 第二个节点
     * @return 最低公共祖先节点
     */
    public static TreeNode getLastCommonParentRec(TreeNode root, TreeNode n1, TreeNode n2) {
    if (findNodeRec(root.left, n1)) { // 如果n1在左子树
        if (findNodeRec(root.right, n2)) { // 如果n2在右子树
            return root; // 返回根节点
        } else { // 如果n2也在左子树
            return getLastCommonParentRec(root.left, n1, n2); // 递归处理
        }
    } else { // 如果n1在右子树
        if (findNodeRec(root.left, n2)) { // 如果n2在左子树
            return root; // 返回根节点
        } else { // 如果n2在右子树
            return getLastCommonParentRec(root.right, n1, n2); // 递归处理
        }
    }
    }

/**
 * 递归判断一个点是否在树里
 * @param root 根节点
 * @param node 查找的节点
 * @return 是否找到该节点
    */
    private static boolean findNodeRec(TreeNode root, TreeNode node) {
    if (node == null || root == null) {
        return false;
    }
    if (root == node) {
        return true;
    }
    // 先尝试在左子树中查找
    boolean found = findNodeRec(root.left, node);
    if (!found) { // 如果查找不到，再在右子树中查找
        found = findNodeRec(root.right, node);
    }
    return found;
    }

/**
 * 9. 树中两个节点的最低公共祖先节点
 * 递归解法2（更简单）
 * @param root 树根节点
 * @param n1 第一个节点
 * @param n2 第二个节点
 * @return 最低公共祖先节点
    */
    public static TreeNode getLastCommonParentRec2(TreeNode root, TreeNode n1, TreeNode n2) {
    if (root == null) {
        return null;
    }
    // 如果有一个match，则说明当前node就是要找的最低公共祖先
    if (root.equals(n1) || root.equals(n2)) {
        return root;
    }
    TreeNode commonLeft = getLastCommonParentRec2(root.left, n1, n2);
    TreeNode commonRight = getLastCommonParentRec2(root.right, n1, n2);
    // 如果一个在左子树找到，一个在右子树找到，则说明root是唯一可能得最低公共祖先
    if (commonLeft != null &amp;&amp; commonRight != null) {
        return root;
    }
    // 其他情况是要不然在左子树要不然在右子树
    if (commonLeft != null) {
        return commonLeft;
    }
    return commonRight;
    }

</code></pre>
			<pre><code>非递归算法：得到从二叉树根节点到两个节点的路径，路径从头开始的最后一个公共节点就是它们的最低公共祖先节点

</code></pre>
			<pre><code class='language-java' lang='java'>    /**
     * 9. 树中两个节点的最低公共祖先节点
     * 非递归
     * @param root 树根节点
     * @param n1 第一个节点
     * @param n2 第二个节点
     * @return 第一个公共祖先节点
     */
    public static TreeNode getLastCommonParent(TreeNode root, TreeNode n1, TreeNode n2) {
    if (root == null || n1 == null || n2 == null) {
        return null;
    }
    ArrayList&lt;TreeNode&gt; p1 = new ArrayList&lt;&gt;();
    boolean res1 = getNodePath(root, n1, p1);
    ArrayList&lt;TreeNode&gt; p2 = new ArrayList&lt;&gt;();
    boolean res2 = getNodePath(root, n2, p2);
    if (!res1 || !res2) {
        return null;
    }
    TreeNode last = null;
    Iterator&lt;TreeNode&gt; iter1 = p1.iterator();
    Iterator&lt;TreeNode&gt; iter2 = p2.iterator();
    while (iter1.hasNext() &amp;&amp; iter2.hasNext()) {
        TreeNode tmp1 = iter1.next();
        TreeNode tmp2 = iter2.next();
        if (tmp1 == tmp2) {
            last = tmp1;
        } else { // 直到遇到非公共节点
            break;
        }
    }
    return last;
    }

/**
 * 把从根节点到node路径上所有的点都添加到path中
 * @param root 树根节点
 * @param node 终点节点
 * @param path 路径
 * @return 是否是目标节点
    */
    public static boolean getNodePath(TreeNode root, TreeNode node, ArrayList&lt;TreeNode&gt; path) {
    if (root == null) {
        return false;
    }
    path.add(root); // 把这个节点添加到路径中
    if (root == node) {
        return true;
    }
    boolean found = false;
    found = getNodePath(root.left, node, path); // 先在左子树中找
    if (!found) {
        found = getNodePath(root.right, node, path);
    }
    if (!found) { // 如果实在没找到证明这个节点不在路径中，删除刚刚那个节点
        path.remove(root);
    }
    return found;
    }

</code></pre>
			<ol start='10'>
				<li>判断是否为二分查找树BST
					递归解法：中序遍历的结果应该是递增的。</li>

			</ol>
			<pre><code class='language-java' lang='java'>    /**
     * 10. 判断是否为二分查找树BST
     * @param root 根节点
     * @param pre 上一个保存的节点
     * @return 是否为BST树
     */
    public static boolean isValidBST(TreeNode root, int pre){
    if (root == null) {
        return true;
    }
    boolean left = isValidBST(root.left, pre);
    if (!left) {
        return false;
    }
    if(root.val &lt;= pre) {
        return false;
    }
    pre = root.val;
    boolean right = isValidBST(root.right, pre);
    if(!right) {
        return false;
    }
    return true;
    }
</code></pre>
			<pre><code>非递归解法：参考非递归中序遍历。
</code></pre>
			<pre><code class='language-java' lang='java'>	/** 
      * 10. 判断是否为二分查找树BST
      * 非递归
      * @param root 根节点
      */
    public boolean isValidBST2(TreeNode root){
    Stack&lt;TreeNode&gt; stack = new Stack&lt;&gt;();
    //设置前驱节点
    TreeNode pre = null;
    while(root != null || !stack.isEmpty()){
        while (root != null) { // 将当前节点，以及左子树一直入栈，循环结束时，root==null
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        //比较并更新前驱，与普通遍历的区别就在下面四行
        if(pre != null &amp;&amp; root.val &lt;= pre.val){
            return false;
        }
        pre = root;
        root = root.right;  //访问右子树
    }
    return true;
    }
</code></pre>
			<!-- <p><a href='https://blog.csdn.net/wyqwilliam/article/details/82935922' target='_blank' class='url'>https://blog.csdn.net/wyqwilliam/article/details/82935922</a></p> -->
		</div>
		<footer>
			<p>Design by <a href="http://cdcoder.cn" target="_blank">徐思润个人博客</a> </p>
			<p>备案号：<a href="/">蜀ICP备15014105号-1</a></p>
			<script type="text/javascript" src="https://s96.cnzz.com/z_stat.php?id=1277229191&web_id=1277229191"></script>
		</footer>
		<script src="../js/rainbow.min.js"></script>
		<script src="../js/java_h.js"></script>
	</body>
</html>
